package leetcode.primary;

public class T91 {
    public int numDecodings(String s) {
        int[] dp = new int[s.length()];
        if (s.charAt(0)!='0'){
            dp[0] = 1;
        }else {
           return  0;
        }
        if (s.length()>=2){
            int temp = (s.charAt(0) - '0') * 10 + s.charAt(1)-'0';
            if (s.charAt(1)!='0'){
                if (temp<=26) {
                    dp[1] = 2;
                }else {
                    dp[1] = 1;
                }
            }else if (s.charAt(1)=='0'){
                if (temp<=26){
                    dp[1] = dp[0];
                }else {
                    return 0;
                }
            }
        }
        if (s.length()>2){
            for (int i = 2; i < s.length(); i++) {
                int temp = (s.charAt(i - 1) - '0') * 10 + s.charAt(i)-'0';
                boolean i_is_zero = s.charAt(i)=='0';
                boolean pre_is_zero = s.charAt(i-1)=='0';
                if (temp<=26 ){
                    if (!i_is_zero && !pre_is_zero ){
                        dp[i] = dp[i-1]+dp[i-2];
                    }else if (i_is_zero && !pre_is_zero){
                        dp[i]=dp[i-2];
                    }else if (i_is_zero){
                        return 0;
                    }else {
                        dp[i] = dp[i-1];
                    }
                }else {
                    if (!i_is_zero && !pre_is_zero ){
                        dp[i] = dp[i-1];
                    }else if (i_is_zero && !pre_is_zero) {
                        return 0;
                    }else if (i_is_zero) {
                        return 0;
                    }
                }

            }
        }
        for (int i : dp) {
            System.out.print(i+" ");
        }
        System.out.println();
        return dp[s.length()-1];
    }

    public static void main(String[] args) {
        T91 t91 = new T91();
        int numDecodings = t91.numDecodings("301");

        System.out.println(numDecodings);
    }
}
